package com.ds.seqlist.LeetCode;

public class Num82_DeleteDuplicates {
//    public ListNode deleteDuplicates(ListNode head) {
//        ListNode dummyHead = new ListNode();
//        dummyHead.next = head;
//        ListNode prev = dummyHead;
//        ListNode cur = prev.next;
//        while (cur != null) {
//            ListNode next = cur.next;
//            if (next == null) {
//                // 当前链表只有一个节点，不可能重复
//                // next走到null，所有节点判断完毕
//                break;
//            }else {
//                // 此时链表至少存在两个有效节点
//                // 不重复
//                if (cur.val != next.val) {
//                    // 三指针后移
//                    prev = prev.next;
//                    cur = cur.next;
//                }else {
//                    // 此时碰到重复元素，一直移动next指针
//                    while (next != null && cur.val == next.val) {
//                        next = next.next;
//                    }
//                    // next指向第一个不重复元素
//                    // prev之后，next之前全是重复元素
//                    prev.next = next;
//                    cur = next;
//                }
//            }
//        }
//        return dummyHead.next;
//    }

    /**
     * 传入一个链表的头节点，就能删除当前链表中所有重复节点，返回删除后的头节点
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 1.边界
        if (head == null || head.next == null) {
            return head;
        }
        // 2.判断头节点是否是待删除的节点
        if (head.val != head.next.val) {
            head.next = deleteDuplicates(head.next);
            return head;
        }else {
            // 先处理头节点
            ListNode nextHead = head.next;
            while (nextHead != null && head.val == nextHead.val) {
                nextHead = nextHead.next;
            }
            // nextHead一定是不重复的新的头节点
            // 以当前新的头节点为链表的节点删除交给子函数
            return deleteDuplicates(nextHead);
        }
    }

}
